import java.io.Serializable;
import java.util.Iterator;


public class QuadTree implements Serializable {

	private TreeNode root = null;
	private int numberOfObjects;
	
	
	public QuadTree()
	{
		root = new TreeNode();
		setNumberOfObjects(0);
	}
	
	public TreeNode getRoot() {
		return root;
	}
	
/*	public String toString()
	{
		return "";
	}
*/	
	public boolean insertWall(Wall wall, TreeNode startNode)
	
	{
		startNode = findNode(wall.getPosition(), startNode);
		if(startNode.isEmpty == false)  // check for collision
		{
			if(detectCollision1(wall, startNode) == true && startNode.getIsWall() == false)
			{		
				// vehicle collision when placing a wall! how unlucky for the other player :P
				// TODO what to do in this situation?
				destroyVehicle(startNode.getPlayerId());
				emptyNode(startNode);
				
			}
			else
			{				
					TreeNode newstartNode = new TreeNode();
					int child1=0,child2=0;
					while(child1 == child2)
					{
						startNode.createChildren(); 
						child1 = chooseChild(wall.getPosition(), startNode);
						child2 = chooseChild(startNode.getPosition(), startNode);
						switch(child2)
						{
						case 1:
							copyNodeToChild(startNode, startNode.getChild1());
							newstartNode = startNode.getChild1();
							break;
						case 2:
							copyNodeToChild(startNode, startNode.getChild2());
							newstartNode = startNode.getChild2();
							break;
						case 3:
							copyNodeToChild(startNode, startNode.getChild3());
							newstartNode = startNode.getChild3();
							break;
						case 4:
							copyNodeToChild(startNode, startNode.getChild4());
							newstartNode = startNode.getChild4();
							break;
						}
						if(child1 != child2)
						{//If the new wall and existing wall are not getting the same child number
							switch(child1){
							case 1:
								fillNodeWithWall(wall, startNode.getChild1());
								break;
							case 2:
								fillNodeWithWall(wall, startNode.getChild2());
								break;
							case 3:
								fillNodeWithWall(wall, startNode.getChild3());
								break;
							case 4:
								fillNodeWithWall(wall, startNode.getChild1());
								break;
							}
							emptyNode(startNode); // only leaves can have data!!!
						}
						else{
							emptyNode(startNode); // only leaves can have data!!!
							startNode = newstartNode;
						}
					}
			}
			
		}
		else
		{
			fillNodeWithWall(wall, startNode); // should MARK that node as full and as a wall
		}
		
		return false;
	}
	
	private void copyNodeToChild(TreeNode startNode, TreeNode child ) {
		
		child.setDirection(startNode.getDirection());
		child.setIsWall(startNode.getIsWall());
		child.setPosition(startNode.getPosition());
		//child.setLength(startNode.getLength());
		//child.setWidth(startNode.getWidth());
		child.setPlayerId(startNode.getPlayerId());
		child.isEmpty = startNode.isEmpty;
		//child.setParent(startNode.getParent());		
		
	}
	
	private void copyNodeToParent(TreeNode startNode, TreeNode parent) {
		
		parent.setDirection(startNode.getDirection());
		parent.setIsWall(startNode.getIsWall());
		parent.setPosition(startNode.getPosition());
		//parent.setLength(startNode.getLength());
		//parent.setWidth(startNode.getWidth());
		parent.setPlayerId(startNode.getPlayerId());
		parent.isEmpty = startNode.isEmpty;		
		
	}

	public boolean insertVehicle(VehiclePos vehicle, TreeNode startNode)
	{
		//FIRST must remove vehicle's previous position from the QuadTree
		if(vehicle.prevPos != null)
		{
			TreeNode tempNode = null;
			tempNode = findNode(vehicle.prevPos, root);
			emptyNode(tempNode);
			cleanupLeaves(tempNode.getParent());
			
		}
		
		// Next, insert the vehicle into the tree
		startNode = findNode(vehicle.pos, startNode);
		if(startNode.isEmpty == false)  // check for collision
		{
			
				if(detectCollision2(vehicle, startNode) == true)// TODO check to see if collision is within tolerance
				{
					if(startNode.getIsWall() == true)  // we need to know if it's a vehicle collision or not
					{
						destroyVehicle(vehicle.playerId);
					}
					else
					{
						destroyVehicle(vehicle.playerId);
						destroyVehicle(startNode.getPlayerId());
						emptyNode(startNode);
						cleanupLeaves(startNode.getParent());
						// vehicle collision for both players! how unlucky for the other player :P
					}
				}
				else // no collision, create more leaves
				{
					TreeNode newstartNode = new TreeNode();
					int child1=0,child2=0;
					while(child1 == child2){
						startNode.createChildren(); 
						child1 = chooseChild(vehicle.pos, startNode);
						child2 = chooseChild(startNode.getPosition(), startNode);
						switch(child2){
						case 1:
							copyNodeToChild(startNode, startNode.getChild1());
							newstartNode = startNode.getChild1();
							break;
						case 2:
							copyNodeToChild(startNode, startNode.getChild2());
							newstartNode = startNode.getChild2();
							break;
						case 3:
							copyNodeToChild(startNode, startNode.getChild3());
							newstartNode = startNode.getChild3();
							break;
						case 4:
							copyNodeToChild(startNode, startNode.getChild4());
							newstartNode = startNode.getChild4();
							break;
						}
						if(child1 != child2){//If the new wall and existing wall are not getting the same child number
							switch(child1){
							case 1:
								fillNodeWithVehicle(vehicle, startNode.getChild1());
								break;
							case 2:
								fillNodeWithVehicle(vehicle, startNode.getChild2());
								break;
							case 3:
								fillNodeWithVehicle(vehicle, startNode.getChild3());
								break;
							case 4:
								fillNodeWithVehicle(vehicle, startNode.getChild1());
								break;
							}
							emptyNode(startNode); // only leaves can have data!!!
						}
						else{
							emptyNode(startNode); // only leaves can have data!!!
							startNode = newstartNode;
						}
					}
				}			
		}
		else
		{
			fillNodeWithVehicle(vehicle, startNode); // should MARK that node as full and as a vehicle
		}
		return false;
	}
	
	public void destroyVehicle(int playerId)
	{
		// This method will remove the vehicle from the vehicle arraylist in the Board.java class
		// This will also kill the player and remove his name from the alivePlayers arrayList
		Iterator<Vehicle> it = Board.vehicleList.iterator();
		Vehicle temp = null;
		for(int i = 0; i < Board.vehicleList.size(); i++)
		{
			temp = it.next();
			if(temp.equals(playerId))
			{
				System.out.println("Vehicle Removed"); // for debugging purposes
				Board.vehicleList.remove(temp);
				Board.numberOfObjects--;
				numberOfObjects--;
			}
		}
		Iterator<Player> it1 = Board.alivePlayers.iterator();
		Player temp1 = null;
		for(int i = 0; i < Board.alivePlayers.size(); i++)
		{
			temp1 = it1.next();
			if(temp1.equals(playerId))
			{
				System.out.println("Player Killed"); // for debugging purposes
				Board.alivePlayers.remove(temp1);
			}
		}
	}
	
	public void cleanupLeaves(TreeNode parentNode)
	{
		int count = 0;
		if(parentNode.getChild1() != null) if(parentNode.getChild1().isEmpty == true) count++;
		if(parentNode.getChild2() != null) if(parentNode.getChild2().isEmpty == true) count++;
		if(parentNode.getChild3() != null) if(parentNode.getChild3().isEmpty == true) count++;
		if(parentNode.getChild4() != null) if(parentNode.getChild4().isEmpty == true) count++;
		if(count >= 3)
		{
			if(parentNode.getChild1() != null) if(parentNode.getChild1().isEmpty == false) copyNodeToParent(parentNode.getChild1(), parentNode);
			if(parentNode.getChild2() != null) if(parentNode.getChild2().isEmpty == false) copyNodeToParent(parentNode.getChild2(), parentNode);
			if(parentNode.getChild3() != null) if(parentNode.getChild3().isEmpty == false) copyNodeToParent(parentNode.getChild3(), parentNode);
			if(parentNode.getChild4() != null) if(parentNode.getChild4().isEmpty == false) copyNodeToParent(parentNode.getChild4(), parentNode);
			parentNode.setChild1(null);
			parentNode.setChild2(null);
			parentNode.setChild3(null);
			parentNode.setChild4(null);
			
		}
	}

	public boolean emptyNode(TreeNode node)
	{
		node.setDirection(0);
		node.setIsWall(true);
		//node.setLength(0);
		node.setPlayerId(0);
		node.setPosition(null);
		//node.setWidth(0);
		node.isEmpty = true;
		node.setRadius(0);
		return true;
	}
	
	
	public boolean fillNodeWithWall(Wall wall, TreeNode node)// should MARK that node as full and as a wall
	{
		
		node.setDirection(wall.getDirection());
		node.setIsWall(true);
		//node.setLength(wall.getLength());
		node.setPlayerId(wall.getPlayerId());
		node.setPosition(wall.getPosition());
		//node.setWidth(wall.getWidth());
		node.setRadius(wall.radius);
		node.isEmpty = false;
		
		return false;
	}
	
	public boolean fillNodeWithVehicle(VehiclePos vehicle, TreeNode node)// should MARK that node as full and as a vehicle
	{
		node.setDirection(vehicle.direction);
		node.setIsWall(false);
		//node.setLength(Board.vehicleLength);
		node.setPlayerId(vehicle.playerId);
		node.setPosition(vehicle.pos);
		//node.setWidth(Board.vehicleWidth);
		node.isEmpty = false;
		node.setRadius(vehicle.radius);
		return false;
	}
	
	public boolean detectCollision2(VehiclePos vehicle, TreeNode node)
	{
		// TODO the math and collision tolerance checks
		double distance = Math.sqrt(Math.pow(node.getPosition().y-vehicle.pos.y,2)+Math.pow(node.getPosition().x-vehicle.pos.x,2));
		if(distance > (vehicle.radius+node.getRadius()))
			return false;
		else 
			{
				System.out.println("COLLISION");
				return true;
			}
	}
	
	public boolean detectCollision1(Wall wall, TreeNode node)
	{
		double distance = Math.sqrt(Math.pow(node.getPosition().y - wall.getPosition().y,2)+Math.pow(node.getPosition().x - wall.getPosition().x,2));
		if(distance > (wall.radius + node.getRadius()))
			return false;
		else 
		{
			System.out.println("COLLISION");
			return true;
		}
	}
	
	public TreeNode findNode(Position pos, TreeNode startNode)
	{
		if (startNode.hasChildren() == true)
		{
			TreeNode childNode = new TreeNode();
			// check for proper child to go to
			switch(chooseChild(pos, startNode))
			{
			case 1:
				childNode = startNode.getChild1();
				startNode = findNode(pos, childNode);
				break;
			case 2:
				childNode = startNode.getChild2(); 
				startNode = findNode(pos, childNode);
				break;
			case 3:
				childNode = startNode.getChild3(); 
				startNode = findNode(pos, childNode);
				break;
			case 4:
				childNode = startNode.getChild4(); 
				startNode = findNode(pos, childNode);
				break;
			}
		}
		else
		{
			return startNode;
		}
		
		return startNode;
	}
	
	public int chooseChild(Position pos, TreeNode parentNode)
	{
		if(pos.x < parentNode.getCenter().x)
		{
			if(pos.y < parentNode.getCenter().y)
			{
				return 1;
			}
			else
			{
				return 3;
			}
		}
		else
		{
			if(pos.y < parentNode.getCenter().y)
			{
				return 2;
			}
			else
			{
				return 4;
			}
		}
	}

	public int getNumberOfObjects() {
		return numberOfObjects;
	}

	public void setNumberOfObjects(int numberOfObjects) {
		this.numberOfObjects = numberOfObjects;
	}
	
	public void printleaves(TreeNode node){
		if(node.hasChildren()){
			printleaves(node.getChild1());
			printleaves(node.getChild2());
			printleaves(node.getChild3());
			printleaves(node.getChild4());
		}
		else{
			if(node.isEmpty == false){
				System.out.println("("+node.getPosition().x+","+node.getPosition().y+")");
			}
		}
	}
	
}
